#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
//题目 1907: [蓝桥杯][算法提高VIP]递推求值
const ll mod=99999999;
struct matrix{
    ll m[10][10];
};
ll f[8]={6,5,1,4,2,3,5,3};
matrix e;//底数矩阵
void init_e(){
    for(ll i=0;i<8;i++){
        for(ll j=0;j<8;j++){
            e.m[i][j]=0;
        }
    }
    e.m[0][1]=e.m[0][4]=e.m[0][6]=1;
    e.m[1][0]=e.m[2][0]=1;
    e.m[3][1]=e.m[4][2]=e.m[5][3]=e.m[6][6]=e.m[7][7]=1;
}
//矩阵a乘以矩阵b
matrix multi(matrix a,matrix b){
    matrix temp;
    memset(temp.m,0,sizeof(temp.m));
    for(ll i=0;i<8;i++){
        for(ll j=0;j<8;j++){
            for(ll k=0;k<8;k++){
                temp.m[i][j]=(temp.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return temp;
}
//矩阵快速幂
matrix quick(matrix a,ll b){
    matrix sum;
    //单位矩阵
    for(ll i=0;i<8;i++)
        for(ll j=0;j<8;j++)
            if(i==j)sum.m[i][j]=1;
            else sum.m[i][j]=0;
    while(b){
        if(b&1){
            sum=multi(sum,a);
        }
        b>>=1;
        a=multi(a,a);
    }
    return sum;
}

int main()
{
    IOS;
    ll n;
    cin>>n;
    if(n<4){
        if(n==1)cout<<2<<endl<<3<<endl;
        else if(n==2)cout<<1<<endl<<4<<endl;
        else cout<<6<<endl<<5<<endl;
        return 0;
    }
    matrix M=quick(e,n-3);
    ll ans[2]={0,0};
    for(ll k=0;k<2;k++){
        for(ll i=0;i<8;i++){
            ans[k]=(ans[k]+M.m[k][i]*f[i])%mod;
        }
    }
    cout<<ans[0]<<endl<<ans[1]<<endl;
    getchar();
    getchar();
    return 0;
}
